Standard moving image coding systems such as ITU-T H. 26x and the MPEG series are known from the prior art. In these standard moving image coding systems, from the viewpoint of the balance between compression efficiency and load, and indeed of the popularization of dedicated LSI, the Discrete cosine transform (referred to as “DCT” hereinbelow) is mainly employed. However, due to the fact that the DCT performs basis coefficient quantization, in cases where encoding is performed at a very low bit rate, the basis, which is key as far as the representation of the original signal is concerned, cannot be restored and, as a result, there is the problem that distortion is generated. As methods for resolving such problems, Matching Pursuits-based image coding systems exist, such as that disclosed by “R. Neff et al, “Very Low Bit-rate Video Coding Based on Matching Pursuits”, IEEE Trans. on CSVT, vol. 7, pp. 158-171, February 1997. Matching Pursuits is a technique for representing an interframe prediction residual signal as the linear sum of an over-complete basis set, and, because the units of the basis representation are not limited to blocks and the possibility exists of it being possible to represent an irregular signal compactly with small number of basis coefficients by means of over-complete basis patterns, Matching pursuits possesses the characteristic of obtaining an image quality that is visually superior to that obtained by DCT encoding at low rate encoding. With Matching Pursuits, a prediction residual image signal f to be encoded can be represented as per the following equation by using an over-complete basis set G prepared in advance that comprises n types of basis gk∈ G (1≦k≦n).
                    f        =                              (                                          ∑                                  i                  =                  0                                                  m                  -                  1                                            ⁢                                                          ⁢                                                〈                                                            S                      i                                        ,                                          g                      ki                                                        〉                                ⁢                                  g                  ki                                                      )                    +                      r            m                                              (        1        )            
Here, m is the total number of basis search steps, i is the basis search step number, and ri is the prediction residual image signal following completion of the basis search of the (i−1)th step, this signal being without further processing the prediction residual image signal for the basis search of the ith step, where r0=f. Further, si and gki are the partial region and basis respectively, these being obtained by selecting, in the basis search of the ith step, a combination of s and gk such that the inner product value thereof is maximized, from optional partial regions s (partial regions in a frame) of ri, as well as optional bases gk contained in the basis set G. If the basis search is performed thus, the larger the number m of basis search steps, the less energy rm possesses. This means that the greater the number of bases used in the representation of the prediction residual image signal f, the better the signal can be represented.
In each of the basis search steps, the data that is encoded is:    1) The index expressing gki (gk is shared and maintained on the encoding side and the decoding side, which makes it possible to specify a basis by converting only the index data).    2) The inner product values <si, gki> (correspond to the basis coefficients), and    3) si on-screen center position data pi=(xi, yi)
A set of these parameters is collectively known as an atom. By means of this image signal representation and encoding method, the number of encoded atoms is increased, that is, as the total number m of basis search steps increases, so too does the encoded volume, whereby distortion is reduced.
Meanwhile, in order to derive the superior performance of Matching Pursuits coding, it is important to efficiently entropy code the atom parameters constituting the data to be encoded. In Matching Pursuits image coding, interframe prediction residual signals are prepared in frame units, and then partial signals which are to be represented are first specified as encoding data in the frame. These partial signals may be in any position in the frame. However, for an ordinary image signal, signal locations where movement is large, that is, that have a large amount of data, may be considered to be locations where the power of the residual signal is large, and hence methods that first detect locations at which the power is maximum in a prediction residual frame as partial signals are typical. Thereupon, such partial signals are basis-represented but such position data in the intraframe must be encoded. As far as the basis representation is concerned, bases that better represent these partial signals are selected from among the bases contained in a pre-provided basis codebook, and the corresponding index, and basis coefficient (the inner product value of the partial signal and the basis) are transmitted and stored as coding data.
Regardless of whether the Matching Pursuits or DCT described above is employed, in a conventional image coding system, the coding parameters have hitherto been entropy-coded by means of Huffman coding after being subjected to signal redundancy reduction and quantization. On the other hand, Huffman coding is subject to the restriction that only integer-length code can be allocated to the symbols to be encoded. Arithmetic coding has been proposed as a means of overcoming this restriction. The principles of arithmetic coding are explained in detail in, among other works, “The Data Compression Book 2nd edition”, Mark Nelson and Jean-Loup Gailly, M&T Books, 1995, for example. The respective typical frequency of occurrence in the alphabet of symbols to be encoded is allocated to an interval on a number line from 0 to 1, and when a certain symbol occurs, the interval to which the symbol belongs is first selected, then, for the next symbol, the interval to which the previous symbol belongs is considered as being from 0 to 1 and the interval to which this next symbol is to belong is selected so as to lie within this interval. Repetition of this operation makes it possible to represent a series of symbols having a finite length in the form of a single numeric value between 0 and 1. It is known from this fact that arithmetic coding is capable of representing the code length for each symbol with decimal precision and that entropy coding efficiency is thus generally superior to Huffman coding.